def insertion(x):
  l = len(x)
  for i in range(1, l):
    key = x[i]

    j = i - 1

    while j >= 0 and x[j] > key:
      x[j+1] = x[j]
      j = j - 1

    x[j+1] = key

  return x

if __name__ == "__main__":
  a = [1,2,4,5]
  b = []
  c = [2,1,4,34,1,3]
  d = ['a','c','b','a','df']

  print insertion(a)
  print insertion(b)
  print insertion(c)
  print insertion(d)
